package leecode.array.其他;

/**
 * @author wangxi created on 2024/8/4 17:40
 * @version v1.0
 *
 * https://leetcode.cn/problems/minimum-window-substring/
 *
 * 利用双指针，先大范围圈出一个窗口，然后开始缩短左边界，知道找到最短的字符串
 */
public class MinWindow {

    public static void main(String[] args) {
        MinWindow minWindow = new MinWindow();
        String s = minWindow.minWindow("ADOBECODEBANC", "ABC");
        System.out.println(s);

        int i = 'A';
        System.out.println(i);  // 输出结果是65，为A的ascII码
    }

    String res = "";
    int min = Integer.MAX_VALUE;
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() <= 0 || t.length() <= 0) {
            return "";
        }
        // 定义两个位数组
        int[] countS = new int[128];
        int[] countT = new int[128];
        for (int i = 0; i < t.length(); i++) {
            countT[t.charAt(i)]++;
        }
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            countS[s.charAt(right)]++;
            while (isCovered(countS, countT)) {
                int curLen = right - left + 1;
                if (curLen < min) {
                    min = curLen;
                    res = s.substring(left, right + 1);
                }
                // 左边字符出去
                countS[s.charAt(left)]--;
                left++;
            }
        }
        return res;
    }

    // 如果使用Map作为位图注意：Map<Character, Integer> Integer是对象，可以intValue()
    private boolean isCovered(int[] countS, int[] countT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (countS[i] < countT[i]) {
                return false;
            }
        }

        for (int i = 'a'; i <= 'z'; i++) {
            if (countS[i] < countT[i]) {
                return false;
            }
        }

        return true;
    }
}
